import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class test {
    // leetcode 2331.计算布尔二叉树的值
    class Solution {
        public boolean evaluateTree(TreeNode root) {
            if(root.left == null && root.right == null){
                return root.val == 1;
            }
            boolean left = evaluateTree(root.left);
            boolean right = evaluateTree(root.right);
            if(root.val == 2){
                return left || right;
            }else {
                return left && right;
            }
        }
    }
    // leetcode 129.求根节点到叶子节点数字之和
    class Solution1 {
        public int sumNumbers(TreeNode root) {
            return dfs(root,0);
        }
        public int dfs(TreeNode root,int sum){
            sum = sum * 10 + root.val;
            if(root.left == null && root.right == null){
                return sum;
            }
            if(root.left == null){
                return dfs(root.right,sum);
            }
            if(root.right == null){
                return dfs(root.left,sum);
            }
            return dfs(root.left,sum) + dfs(root.right,sum);
        }
    }
    // leetcode 814.二叉树剪枝
    class Solution2 {
        public TreeNode pruneTree(TreeNode root) {
            if(dfs1(root,0) == 0){
                return null;
            }
            TreeNode cur = dfs2(root);
            return cur;
        }
        // 1. 求和法
        public int dfs1(TreeNode root,int sum){
            if(root == null){
                return 0;
            }
            int left = dfs1(root.left,sum);
            int right = dfs1(root.right,sum);
            if(left == 0){
                root.left = null;
            }
            if(right == 0){
                root.right = null;
            }
            return root.val + left + right;
        }
        // 2. 叶子0节点法
        public TreeNode dfs2(TreeNode root){
            if(root == null){
                return null;
            }
            root.left = dfs2(root.left);
            root.right = dfs2(root.right);
            if(root.left == null && root.right == null && root.val == 0){
                return null;
            }
            return root;
        }
    }
    // leetcode 98.验证二叉搜索树
    class Solution {
        public long tmp = Long.MIN_VALUE;

        public boolean isValidBST(TreeNode root) {
            return dfs(root);
        }

        public boolean dfs(TreeNode root) {
            if (root == null) {
                return true;
            }
            boolean left = dfs(root.left);
            // 剪枝
            if (root.val <= tmp) {
                return false;
            }
            tmp = root.val;
            boolean right = dfs(root.right);
            return left && right;
        }
    }
}
